package org.example.myleet.binarysearch;

import org.example.myleet.Utils.*;
import org.example.myleet.model.CustomFunction;

import java.util.*;

public class BinarySearchSolution {

    //面试题 04.06。二叉搜索树搜索
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (null != p.right) {
            TreeNode cur = p.right;
            while (null != cur.left) {
                cur = cur.left;
            }
            return cur;
        }
        TreeNode successor = null;
        TreeNode node = root;
        while (node != null) {
            if (node.val > p.val) {
                successor = node;
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return successor;
    }

    //p4
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        //求中位数忽略奇偶情况的巧妙做法
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findTheKthNumber(nums1, 0, nums2, 0, left) + findTheKthNumber(nums1, 0, nums2, 0, right)) / 2.0;
    }
    private double findTheKthNumber(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length) {
            //i超出了nums1，说明目标应该落在nums2中，j+k保持是第(m+n+2)/2个位置的数，而下标是-1得到的
            return nums2[j + k-1];
        }
        if (j >= nums2.length) {
            //i超出了nums2，说明目标应该落在nums1中，i+k保持是第(m+n+1)/2个位置的数，而下标是-1得到的
            return nums1[i + k-1];
        }
        if (k == 1) {
            //重合了，二分法查找结束，还是因为下标位置-1，所以应该取排序升序在左边的数，小的数
            return Math.min(nums1[i], nums2[j]);
        }
        //i前进k/2，下标是位置-1
        int idx1 = i + k/2 - 1;
        int midVal1 = (idx1 < nums1.length) ? nums1[idx1] : Integer.MAX_VALUE;
        //j前进k/2，下标是位置-1
        int idx2 = j + k/2 - 1;
        int midVal2 = (idx2 < nums2.length) ? nums2[idx2] : Integer.MAX_VALUE;
        //比较两个中位数大小，取排序升序在左边的数，小的数
        if (midVal1 < midVal2) {
            return findTheKthNumber(nums1, i + k/2, nums2, j, k - k/2);
        } else {
            return findTheKthNumber(nums1, i, nums2, j + k/2, k - k/2);
        }
    }

    //p34
    public int[] searchRange(int[] nums, int target) {
        if (nums.length < 5) {
            //长度太短的直接遍历
            int[] result = new int[]{-1,-1};
            for (int i=0; i<nums.length; i++) {
                if (nums[i] == target && result[0] < 0) {
                    //找到开始
                    result[0] = i;
                }
                if (result[0] > -1) {
                    if (nums[i] != target) {
                        //找到结尾
                        result[1] = i-1;
                        break;
                    }
                    if (i == nums.length-1) {
                        result[1] = i;
                        break;
                    }
                }
            }
            return result;
        }
        //在有序的序列中使用二分法查找目标值
        int left = 0, right = nums.length-1;
        int mid = (left + right) / 2;
        while (left <= right && nums[mid] != target) {
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = (left + right) / 2;
        }
        if (nums[mid] != target) {
            //找不到
            return new int[]{-1,-1};
        }
        //找到target的其中一个位置，前后刷出范围
        int[] result = new int[2];
        int start = mid, end = mid;
        while (start > -1 && nums[start] == target) {
            --start;
        }
        result[0] = start + 1;
        while (end < nums.length && nums[end] == target) {
            ++end;
        }
        result[1] = end - 1;
        return result;
    }

    //p35
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = ((r - l) >> 1) + l;
            if (nums[m] > target) {
                r = m - 1;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                return m;
            }
        }
        if (nums[r] < target) {
            return r + 1;
        }
        if (nums[l] < target) {
            return l + 1;
        }
        return l;
    }

    //剑指Offer 53
    public int searchJ53(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int higherIdx = findTargetIdxOffer53(nums, target, true);
        if (higherIdx < 0) {
            return 0;
        }
        int lowerIdx = findTargetIdxOffer53(nums, target, false);
        return higherIdx - lowerIdx + 1;
    }
    private int findTargetIdxOffer53(int[] nums, int target, boolean higher) {
        int l = 0, r = nums.length - 1;
        if (l == r) {
            if (nums[l] == target) {
                return l;
            }
            return -1;
        }
        while (r - l > 1) {
            int m = (r + l) / 2;
            if (nums[m] < target) {
                l = m;
            } else if (nums[m] > target) {
                r = m;
            } else {
                if (higher) {
                    l = m;
                } else {
                    r = m;
                }
            }
        }
        if (nums[l] == target && nums[l] == nums[r]) {
            if (higher) {
                return r;
            } else {
                return l;
            }
        } else {
            if (nums[l] == target) {
                return l;
            }
            if (nums[r] == target) {
                return r;
            }
        }
        return -1;
    }


    /**
     * 74【二分查找】搜索二维矩阵
     * 0 ms
     * 先纵向二分法找到结果或行，然后再横向二分法找到结果
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int l = 0, r = matrix.length-1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (matrix[mid][0] == target) {
                return true;
            } else if (matrix[mid][0] > target) {
                r = mid;
            } else {
                l = mid;
            }
        }
        int row;
        //左右指针相邻，需要决定用那个指针指向的行
        if (matrix[l][0] == target || matrix[r][0] == target) {
            return true;
        } else if (matrix[r][0] > target) {
            row = l;
        } else {
            row = r;
        }
        l = 0;
        r = matrix[row].length-1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] > target) {
                r = mid;
            } else {
                l = mid;
            }
        }
        //左右指针相邻，查看最终结果
        if (matrix[row][l] == target || matrix[row][r] == target) {
            return true;
        }
        return false;
    }

    /**
     * 81【二分查找】搜索旋转排序数组 II
     * 1 ms
     * 由于可能出现重复元素，所以前半段直接用遍历方式寻找target或者旋转点
     * 找到旋转点后，后半段严格升序，可以用二分法
     */
    public boolean search(int[] nums, int target) {
        if (nums[0] == target) {
            return true;
        }
        int partitionIdx = 0;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] == target) {
                return true;
            }
            if (nums[i-1] > nums[i]) {
                partitionIdx = i;
                break;
            }
        }
        int l = partitionIdx, r = nums.length - 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] > target) {
                r = mid;
            }
            if (nums[mid] < target) {
                l = mid;
            }
        }
        if (nums[l] == target) {
            return true;
        }
        if (nums[r] == target) {
            return true;
        }
        return false;
    }

    /**
     * 153【二分查找】寻找旋转排序数组中的最小值
     * 0 ms
     * 由于没有重复的元素，所以可以使用二分查找，中间位置与左指针位置相比更大时往左指针右移，反之右指针左移，直到找到翻转产生的跳跃位置
     */
    public int findMin(int[] nums) {
        int n = nums.length;
        if (n == 1 || nums[0] < nums[n-1]) {
            return nums[0];
        }
        int l = 0, r = n - 1;
        while (r - l > 1) {
            int mid = (r + l) / 2;
            if (nums[mid] > nums[l]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return Math.min(nums[l], nums[r]);
    }

    /**
     * 154【二分查找】寻找旋转排序数组中的最小值 II
     * 0 ms
     * 二分查找，在存在重复元素的情况下做特殊处理，注意旋转点左右两边的元素，左边元素严格大于等于右边的元素
     * 左中右三个指针只有以下4种情况，按照不同情况处理
     * 1、最简单的，左元素 < 右元素，此时左指针落到最小元素上，直接找到结果，除此情况以外，左元素严格大于等于右元素
     * 2、中元素 == 右元素，此时因为重复元素存在，并不能将中元素左边或右边的元素忽略，不过可以确定的是左元素和右元素的值相等，就把左元素和右元素忽略掉，++l、--r
     * 3、中元素 > 右元素，此时可以确定中元素是在旋转点的左边（旋转点的左边的元素严格大于等于右元素），则中元素左边的元素可以忽略，左指针移到中元素位置
     * 4、中元素 < 右元素，此时可以确定中元素是在旋转点的右边（旋转点右边至右元素严格小于等于右元素），则中元素右边的元素可以忽略，右指针移到中元素位置
     */
    public int findMin154(int[] nums) {
        int l = 0, r = nums.length - 1;
        if (nums[l] < nums[r]) {
            return nums[l];
        }
        while (r - l > 1) {
            if (nums[l] < nums[r]) {
                return nums[l];
            }
            int mid = (l + r) / 2;
            if (nums[mid] == nums[r]) {
                ++l;
                --r;
            } else if (nums[mid] > nums[r]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return Math.min(nums[l], nums[r]);
    }

    /**
     * 162【二分查找】寻找峰值
     */
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1, m;
        while (r - l > 1) {
            m = (r + l) / 2;
            if (nums[m - 1] < nums[m]) {
                if (nums[m] < nums[m + 1]) {
                    //递增上坡，左边界右移
                    l = m + 1;
                } else {
                    //峰值，nums[m - 1] < nums[m] > nums[m + 1]，返回下标
                    return m;
                }
            } else {
                //递减下坡，右边界左移，nums[m - 1] > nums[m]
                r = m - 1;
            }
        }
        //最后相邻的点进行决战比较获得峰值下标
        return nums[l] > nums[r] ? l : r;
    }

    /**
     * 167 【二分法查找】两数之和 II - 输入有序数组
     * n*log(n)
     */
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            if (numbers[i] > target) {
                break;
            }
            int t = target - numbers[i];
            int l = i + 1, r = numbers.length - 1;
            while (l <= r) {
                int m = (r - l) / 2 + l;
                if (numbers[m] > t) {
                    r = m - 1;
                } else if (numbers[m] < t) {
                    l = m + 1;
                } else {
                    return new int[]{i + 1, m + 1};
                }
            }
        }
        return new int[]{0, 0};
    }

    /**
     * 240【二分查找】搜索二维矩阵 II
     * 简单思路，在每个对角线位置进行横竖的二分查找
     */
    public boolean searchMatrix240(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0, j = 0; i < m && j < n;) {
            if (matrix[i][j] < target) {
                if (searchVertical(matrix, target, i, j, m) || searchHorizontal(matrix, target, i, j, n)) {
                    return true;
                }
            } else if (matrix[i][j] > target) {
                break;
            } else {
                return true;
            }
            ++i;
            ++j;
        }
        return false;
    }
    private boolean searchVertical(int[][] matrix, int target, int row, int col, int m) {
        int l = row, r = m - 1, mid;
        while (r - l > 1) {
            mid = (l + r) / 2;
            if (matrix[mid][col] < target) {
                l = mid;
            } else if (matrix[mid][col] > target) {
                r = mid;
            } else {
                return true;
            }
        }
        return matrix[l][col] == target || matrix[r][col] == target;
    }
    private boolean searchHorizontal(int[][] matrix, int target, int row, int col, int n) {
        int l = col, r = n - 1, mid;
        while (r - l > 1) {
            mid = (l + r) / 2;
            if (matrix[row][mid] < target) {
                l = mid;
            } else if (matrix[row][mid] > target) {
                r = mid;
            } else {
                return true;
            }
        }
        return matrix[row][l] == target || matrix[row][r] == target;
    }

    /**
     * 275【二分查找】H 指数 II
     */
    public int hIndex(int[] citations) {
        int N = citations.length;
        int l = 0, r = N - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (citations[m] >= N - m) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return N - l;
    }


    /**
     * 352【有序集合、二分查找】将数据流变为多个不相交区间
     */
    static class SummaryRanges {
        private int size;
        private int[][] ranges;
        public SummaryRanges() {
            size = 0;
            ranges = new int[30001][2];
        }
        /**
         * 思路：维护有序集合，并利用二分法快速找到目标位置进行数字添加
         */
        public void addNum(int val) {
            if (size == 0) {
                ranges[size++] = new int[]{val, val};
            } else {
                //二分法查找离val最近的范围，优先是包含val的区间，其次是val左边的区间，如果找不到才是第0个区间
                int idx = find(val);
                if (val < ranges[idx][0] - 1) {
                    //val在idx区间的左侧且无交集，此时idx=0，并且val自成一个区间，其余所有区间右移
                    forward(idx);
                    ranges[idx] = new int[]{val, val};
                }
                if (val >= ranges[idx][0] - 1) {
                    //val在idx区间的左边界的右边，可以确定idx区间的左边界
                    ranges[idx][0] = Math.min(ranges[idx][0], val);
                }
                if (val <= ranges[idx][1] + 1) {
                    //val在idx区间的右边界的左边，可以确定idx区间的右边界
                    ranges[idx][1] = Math.max(ranges[idx][1], val);
                }
                if (ranges[idx][1] + 1 < val) {
                    //val在idx区间的右侧且无交集，因此需要考察idx+1区间的情况
                    if (idx + 1 < size) {
                        //idx+1区间存在，考察idx+1区间的情况
                        if (val < ranges[idx + 1][0] - 1) {
                            //val在idx+1区间的左侧且无交集，需要右移idx+1区间以及之后的所有区间，然后添加val自成的区间
                            forward(idx + 1);
                            ranges[idx + 1] = new int[]{val, val};
                        } else {
                            //val在idx+1区间内，融合val和idx+1区间
                            if (val >= ranges[idx + 1][0] - 1) {
                                ranges[idx + 1][0] = Math.min(ranges[idx + 1][0], val);
                            }
                            if (val <= ranges[idx + 1][1] + 1) {
                                ranges[idx + 1][1] = Math.max(ranges[idx + 1][1], val);
                            }
                        }
                    } else {
                        //idx区间已经是最右侧的区间，此时在最右侧的区间添加val自成的区间
                        ranges[size++] = new int[]{val, val};
                    }
                }
                if (idx + 1 < size && ranges[idx][1] >= ranges[idx + 1][0] - 1) {
                    //由于val影响了idx区间和idx+1区间，如果idx+1区间存在，且两个区间有交集，则融合idx区间和idx+1区间
                    ranges[idx][1] = ranges[idx + 1][1];
                    backward(idx + 1);
                }
            }
        }
        public int[][] getIntervals() {
            int[][] result = new int[size][2];
            System.arraycopy(ranges, 0, result, 0, size);
            return result;
        }
        /**
         * 找到ranges中第一个ranges[i]包含num的位置i
         * 或第一个ranges[i][1]小于num的位置i
         * 或第0位置（当ranges中没有比num大的区间）
         */
        private int find(int num) {
            int l = 0, r = size - 1, m;
            while (r - l > 1) {
                m = (r + l) / 2;
                if (num < ranges[m][0]) {
                    r = m;
                } else if (ranges[m][1] < num) {
                    l = m;
                } else {
                    return m;
                }
            }
            if (ranges[r][1] < num) {
                return r;
            }
            return l;
        }
        /**
         * 整体往右移动一个位置，用于插入前腾出位置，最终idx位置可以放入新元素
         */
        private void forward(int idx) {
            if (idx < size) {
                for (int i = size; i > idx; --i) {
                    ranges[i] = ranges[i - 1];
                }
            }
            ++size;
        }
        /**
         * 整体往左移动一个位置，用于删除idx位置
         */
        private void backward(int idx) {
            for (int i = idx; i < size; ++i) {
                ranges[i] = ranges[i + 1];
            }
            --size;
        }
    }

    //p729
    static class MyCalendar {

        private List<int[]> ranges;

        public MyCalendar() {
            ranges = new ArrayList<>();
        }

        public boolean book(int start, int end) {
            if (ranges.isEmpty()) {
                ranges.add(new int[]{start, end});
                return true;
            }
            //二分查找离start和end最近的一个区间
            int l = 0, r = ranges.size() - 1, m;
            while (l < r) {
                m = (l + r) >>> 1;
                int[] range = ranges.get(m);
                if (start <= range[0]) {
                    r = m;
                } else if (range[1] <= start) {
                    l = m + 1;
                } else {
                    return false;
                }
            }
            int[] range0 = ranges.get(l);
            if (range0[0] <= start && start < range0[1]) {
                //如果查询结果区间包含了start，则说明区间已经被占据
                return false;
            }
            if (start <= range0[0] && range0[0] < end) {
                //如果查询结果区间的右边界在start和end中间，则说明区间已经被占据
                return false;
            }
            if (end <= range0[0]) {
                //如果查询结果在[start, end]区间的右边，则在将[start, end]区间插在l位置
                ranges.add(l, new int[]{start, end});
                return true;
            }
            if (l == ranges.size() - 1) {
                //l位置已经是ranges的结尾，则[start, end]区间追加在结尾
                ranges.add(new int[]{start, end});
                return true;
            }
            int[] range1 = ranges.get(l + 1);
            if (end <= range1[0]) {
                //如果查询结果在[start, end]区间的左边，则在将[start, end]区间插在l+1位置
                ranges.add(l + 1, new int[]{start, end});
                return true;
            }
            return false;
        }
    }

    private static final int MOD = 1000000007;

    //p878
    public int p878NthMagicalNumber(int n, int a, int b) {
        long c = MathUtil.lcm(a, b);
        long l = Math.min(a, b);
        long r = n * l;
        while (l <= r) {
            long x = (l + r) >> 1;
            long y = x / a + x / b - x / c;
            if (y >= n) {
                r = x - 1;
            } else {
                l = x + 1;
            }
        }
        return (int) ((r + 1) % MOD);
    }

    //p1235
    public int p1235JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; ++i) {
            jobs[i][0] = startTime[i];
            jobs[i][1] = endTime[i];
            jobs[i][2] = profit[i];
        }
        Arrays.sort(jobs, ((o1, o2) -> {
            if (o1[1] == o2[1]) {
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        }));
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            int j = binarySearch(jobs, i - 1, jobs[i - 1][0]);
            dp[i] = Math.max(dp[i - 1], dp[j] + jobs[i - 1][2]);
        }
        return dp[n];
    }

    private int binarySearch(int[][] jobs, int end, int targetEndTime) {
        int start = 0;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (jobs[mid][1] > targetEndTime) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    //p1237
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> answer = new LinkedList<>();
        for (int x = 1; x <= 1000; ++x) {
            int l = 1, r = 1000, y;
            while (l < r) {
                y = (l + r) >> 1;
                int result = customfunction.f(x, y);
                if (result < z) {
                    l = y + 1;
                } else if (result > z) {
                    r = y;
                } else  {
                    List<Integer> a = new ArrayList<>(2);
                    a.add(x);
                    a.add(y);
                    answer.add(a);
                    break;
                }
            }
        }
        return answer;
    }

    /**
     * 1488【有序集合二分查找】避免洪水泛滥
     */
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        //对搜集到的晴天放入有序集合进行排序
        TreeSet<Integer> sunnyDays = new TreeSet<>();
        //记录湖泊下雨的最新时间
        Map<Integer, Integer> filled = new HashMap<>(n - sunnyDays.size());
        int[] answer = new int[n];
        for (int i = 0; i < n; ++i) {
            if (rains[i] != 0) {
                //不是晴天
                if (filled.containsKey(rains[i])) {
                    //这个湖泊之前下过雨，为避免泛滥，需要在之前的下雨后最近的晴天进行抽水
                    //id为这个湖泊上次下雨的时间
                    int lastRainyDay = filled.get(rains[i]);
                    //ceiling使用二分查找，查找这个湖泊上次下雨之后最近的晴天
                    Integer sunnyDay = sunnyDays.ceiling(lastRainyDay);
                    if (null == sunnyDay) {
                        //如果没有这样的晴天，即没有避免泛滥的解决方案，题目要求返回空数组
                        return new int[0];
                    }
                    //这个晴天被用于抽这个湖泊的水
                    answer[sunnyDay] = rains[i];
                    //这个晴天被用掉了
                    sunnyDays.remove(sunnyDay);
                }
                //记录湖泊下雨的最新时间
                filled.put(rains[i], i);
                //下雨，这天不能抽水
                answer[i] = -1;
            } else {
                //记录晴天
                sunnyDays.add(i);
            }
        }
        while (!sunnyDays.isEmpty()) {
            //剩余的晴天全部标记为抽第一个湖的
            //也可以改成初始化answer的时候全部填1，这样更快，不用把sunnyDays全部退出
            answer[sunnyDays.pollFirst()] = 1;
        }
        return answer;
    }

    /**
     * 1552【排序+二分查找】两球之间的磁力
     */
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int n = position.length, l = 1, r = position[n - 1] - position[0], answer = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int i = 2, j = 2, prev = position[0], curr = position[1];
            while (j <= m) {
                while (curr - prev < mid && i < n) {
                    curr = position[i++];
                }
                if (curr - prev >= mid) {
                    ++j;
                    prev = curr;
                } else break;
            }
            if (j <= m) {
                r = mid - 1; //存在还没分配完的小球，mid值不合法，缩小上界
            } else {
                answer = Math.max(answer, mid);
                l = mid + 1; //mid值合法，扩大下界
            }
        }
        return answer;
    }

    /**
     * 1760【排序+二分查找】袋子里最少数目的球
     */
    public int minimumSize(int[] nums, int maxOperations) {
        Arrays.sort(nums);
        int n = nums.length;
        int maxBagSize = n + maxOperations; //每次拆一袋球变两袋球，所以最终最多有n+maxOperation袋球
        int l = 1, r = nums[n - 1];
        while (l < r) {
            int m = (l + r) >> 1;
            boolean valid = true;
            int bagSize = 0;
            for (int i = n - 1; i >= 0; --i) {
                bagSize += nums[i] / m;
                if (nums[i] % m != 0) ++bagSize;
                if (bagSize > maxBagSize) {
                    //如果按最多m个球一袋的情况去分球，结果袋子数超出上线，则不是一种可行的方案
                    valid = false;
                    break;
                }
            }
            if (!valid) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }

    //p1802
    public int maxValue(int n, int index, int maxSum) {
        int l = 1, r = maxSum;
        while (r - l > 1) {
            int mid = (r + l) / 2; //从index开始向右等差（d=1）递减
            int mid1 = mid - 1; //从index-1开始向左等差（d=1）递减
            //计算index左边（不包含index）的等差序列和，注意题目要求最小也要是1，所以当mid1 < index时，等差数列的a0是从1开始的，再往左边的数字都是1
            long sumLeft = mid1 < index ? ((index - mid1) + (long) (1 + mid1) * mid1 / 2) : (((long) (mid1 - (index - 1) + mid1) * index) / 2);
            //计算index右边（包含index）的等差序列和，注意题目要求最小也要是1，所以当mid < (n - index)时，等差数列的a0是小到1为止的，再往右边的数字都是1
            long sumRight = mid < (n - index) ? ((n - index - mid) + (long) (1 + mid) * mid / 2) : (((long) (mid - (n - index - 1) + mid) * (n - index)) / 2);
            if (sumLeft + sumRight > maxSum) {
                r = mid;
            } else {
                l = mid;
            }
        }
        int r1 = r - 1;
        long sumLeft = r1 < index ? ((index - r1) + (long) (1 + r1) * r1 / 2) : (((long) (r1 - (index - 1) + r1) * index) / 2);
        long sumRight = r < (n - index) ? ((n - index - r) + (long) (1 + r) * r / 2) : (((long) (r - (n - index - 1) + r) * (n - index)) / 2);
        int result = (sumLeft + sumRight) > maxSum ? l : r;
        return result;
    }

    //p1818
    /**
     * 思路：从暴力的角度考虑，先遍历一次nums1，计算得到绝对差值和
     * 然后再遍历一次nums2，并且针对每个num2，遍历nums1，寻找离num2最近的num1（题目中提到的可以替换一个num1），获得一个绝对差值下降量
     * 最后知道绝对差值的最大下降量，从绝对差值和中减去就可以得到答案，暴力方法的复杂度是O(n^2)
     * 加速：寻找离num2最近的num1这个步骤通过一个有序的nums1数组结合二分查找就可以找到最近的num1，复杂度为O(log(n))，这样nums2遍历完
     * 寻找绝对差值的最大下降量的复杂度为O(n*log(n))，又因为这个遍历可以和计算绝对差值和一起做，所以最终复杂度为O(n*log(n))
     */
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int mod = 1000000007;
        //复制一个nums1并排序做辅助数组
        int[] copyNums1 = Arrays.copyOf(nums1, nums1.length);
        Arrays.sort(copyNums1);
        //绝对差值和
        long sum = 0L;
        //绝对差值的最大下降量
        int maxDecline = 0;
        for (int i = 0; i < nums1.length; ++i) {
            //求第i个位置上的绝对差值
            int num1 = nums1[i];
            int num2 = nums2[i];
            int difference = Math.abs(num1 - num2);
            sum += difference;
            if (sum - maxDecline > mod) {
                //如果减去绝对差值后sum仍然大于mod，需要进行求余
                sum %= mod;
            }
            //寻找离num2最近的num1，更新绝对差值的最大下降量
            int closestNumber = findClosestNumber(copyNums1, num2);
            int decline = Math.abs(closestNumber - num2);
            maxDecline = Math.max(maxDecline, Math.abs(difference - decline));
        }
        return (int) (sum - maxDecline);
    }
    /**
     * 二分查找找到nums中离target距离（绝对值）最接近的数
     * 复杂度为O(log(n))
     */
    private int findClosestNumber(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (r - l > 1) {
            int m = (r + l) / 2;
            int t = nums[m] - target;
            if (t > 0) {
                r = m;
            } else if (t < 0) {
                l = m;
            } else {
                return nums[m];
            }
        }
        //最后需要比较一下两边哪个更近一点
        return Math.abs(nums[r] - target) < Math.abs(nums[l] - target) ? nums[r] : nums[l];
    }

    //p1828
    public int[] countPoints(int[][] points, int[][] queries) {
        Arrays.sort(points, Comparator.comparingInt(o -> o[0]));
        int[] answer = new int[queries.length];
        for (int j = 0; j < queries.length; ++j) {
            int cnt = 0;
            int[] query = queries[j];
            int x = query[0] - query[2];
            int l1 = 0, r1 = points.length;
            while (l1 < r1) {
                int m = (l1 + r1) >> 1;
                int[] point = points[m];
                if (point[0] < x) {
                    l1 = m + 1;
                } else {
                    r1 = m;
                }
            }
            for (int i = Math.max(0, l1 - 2); i < points.length; ++i) {
                int[] point = points[i];
                if ((point[0] - query[0]) * (point[0] - query[0]) + (point[1] - query[1]) * (point[1] - query[1]) <= query[2] * query[2]) {
                    //圆的数学公式，(x - a)^2 + (y - b)^2 = r^2
                    ++cnt;
                }
            }
            answer[j] = cnt;
        }
        return answer;
    }

    //p2055
    public int[] platesBetweenCandles(String s, int[][] queries) {
        List<Integer> candleIndexes = new ArrayList<>();
        Map<Integer, Integer> candleLeftPlateCount = new HashMap<>();
        char[] charArr = s.toCharArray();
        int plateCount = 0;
        for (int i = 0; i < charArr.length; ++i) {
            if (charArr[i] == '|') {
                candleIndexes.add(i);
                candleLeftPlateCount.put(i, plateCount);
            } else {
                //condition of '*'(plate)
                ++plateCount;
            }
        }
        int[] result = new int[queries.length];
        if (1 > candleIndexes.size()) {
            return result;
        }
        for (int i = 0; i < queries.length; ++i) {
            int leftCandle = binarySearch2055(candleIndexes, queries[i][0], false);
            int rightCandle = binarySearch2055(candleIndexes, queries[i][1], true);
            if (leftCandle < rightCandle) {
                result[i] = candleLeftPlateCount.get(rightCandle) - candleLeftPlateCount.get(leftCandle);
            }
        }
        return result;
    }

    private int binarySearch2055(List<Integer> candleIndexes, int target, boolean smaller) {
        int l = 0, r = candleIndexes.size(), m, index;
        while (l < r) {
            m = (l + r) >>> 1;
            index = candleIndexes.get(m);
            if (index == target) {
                return index;
            } else if (index < target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        if (l < 1) {
            return candleIndexes.get(0);
        }
        if (smaller || l >= candleIndexes.size()) {
            return candleIndexes.get(l - 1);
        }
        return candleIndexes.get(l);
    }

    /**
     * 2560【二分查找+动态规划】打家劫舍 IV
     */
    public int minCapability(int[] nums, int k) {
        int n = nums.length;
        if (n < 2) return nums[0];
        //先找出二分查找的上界和下界，分别是数组最大值和最小值
        int mn = Integer.MAX_VALUE, mx = Integer.MIN_VALUE;
        for (int num : nums) {
            mn = Math.min(mn, num);
            mx = Math.max(mx, num);
        }
        int l = mn, r = mx;
        while (l < r) {
            //m代表二分查找中某一回合尝试的最大窃取金额
            int m = (l + r) >> 1;
            //下面用动态规划验证是否可以实现这个最大窃取金额，dp0和dp1分别记录遍历位置当前最多可以窃取到小于等于m的金额的户数
            int dp0 = nums[0] <= m ? 1 : 0;
            int dp1 = Math.max(dp0, nums[1] <= m ? 1 : 0);
            for (int i = 2; i < n; ++i) {
                //dpi的递推关系是：要么不窃取第i户，则最多窃取到小于等于m的金额的户数等于dp1；要么窃取第i户，若金额小于等于m，则等于dp0+1，否则不能窃取第i户
                int dpi = Math.max(dp1, dp0 + (nums[i] <= m ? 1 : 0));
                dp0 = dp1;
                dp1 = dpi;
            }
            //最终最大窃取户数若能不小于k，说明最大窃取金额m可行
            boolean pass = Math.max(dp0, dp1) >= k;
            if (pass) {
                //缩小右边界
                r = m;
            } else {
                //缩小左边界，由于m不可行，因此左边界收缩为m+1
                l = m + 1;
            }
        }
        return l;
    }

    /**
     * 2594【二分查找】修车的最少时间
     */
    public long repairCars(int[] ranks, int cars) {
        long l = 0, r = (long) ranks[0] * cars * cars;
        while (l < r) {
            long m = (l + r) >> 1;
            boolean canRepair = false;
            int carAmount = cars;
            for (int rank : ranks) {
                carAmount -= (int) Math.sqrt(m / rank);
                if (carAmount < 0) {
                    canRepair = true;
                    break;
                }
            }
            if (!canRepair) {
                canRepair = carAmount <= 0;
            }
            if (canRepair) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

    /**
     * 2824【排序+二分查找】统计和小于目标的下标对数目
     */
    public int countPairs(List<Integer> nums, int target) {
        Integer[] numbers = nums.toArray(new Integer[0]);
        Arrays.sort(numbers);
        int answer = 0, n = numbers.length;
        for (int i = 0; i < n; ++i) {
            int l = 0, r = n - 1, t = target - numbers[i] - 1, m = 0;
            while (l < r) {
                m = (l + r) >> 1;
                if (numbers[m] > t) {
                    r = m;
                } else if (numbers[m] < t) {
                    l = m + 1;
                } else {
                    l = m;
                    break;
                }
            }
            while (l > - 1 && numbers[l] > t) --l;
            while (l > - 1 && l < n - 1 && numbers[l] == numbers[l + 1]) ++l;
            answer += Math.max(0, l - i);
        }
        return answer;
    }

    public static void main(String[] args) {
        BinarySearchSolution solution = new BinarySearchSolution();
        Assert.isTrue(3 == solution.maxDistance(new int[]{1,2,3,4,5,6,7,8,9,10}, 4));
        Assert.isTrue(3 == solution.maxDistance(new int[]{1,2,3,4,7}, 3));

//        Assert.isTrue(7 == solution.minimumSize(new int[]{7,17}, 2));
    }
}
